package Algorithm.sort.basic;

import java.util.Arrays;

/**
 * 快速排序：在一趟快速排序，选择一个元素作为基准将待排序记录分割成两部分，左半部分元素均小于等于基准元素，右半部分元素均大于等于基准元素，这样就确定
 * 了这个基准元素在序列中的位置，再分别对这两部分元素进行快速排序，这样递归执行下去直到无法再分割。每一趟快排都能确定其中一个元素的位置。
 *
 * 时间复杂度：快排的运行时间与划分是否对称有关，平均O(nlogn)，最好O(nlogn)，最坏情况是每次都划分出n-1个元素和0个元素，即对应初始排序表基本有序或基本逆序时，时间复杂度为O(n2)。
 *
 * 空间复杂度：使用了递归工作栈，其容量与递归调用的最大深度一致，空间复杂度平均情况O(logn)，最好情况O(logn)，最坏情况进行n-1次递归调用，所以栈的深度为O(n)。
 *
 * 稳定性：在划分中，若右端有两个关键字相同且均小于基准，则它们被放到左端后相对位置会发生变化，因此快速排序算法不稳定
 *
 * 适用场景：数据量大，数据较为无序的场景
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] A = new int[]{9, 8,7,6,5,4};
        quickSort(A, 0, A.length - 1);
        System.out.println(Arrays.toString(A));
    }

    static void quickSort(int[] A, int low, int high) {
        if(low<high) {
            int pivotPos=partition(A,low,high);//划分
            quickSort(A,low,pivotPos-1);//依次对两个子表进行递归排序
            quickSort(A,pivotPos+1,high);
        }
    }

    //一趟划分 初始时将low指向的元素pivot设为基准元素 最后返回基准元素最终存放位置
    //low指针与high指针交替扫描向中间移动，当high指针扫到比pivot小的元素时，将其移动到low指针指向的空位置，轮到low指针向右扫描
    //low指针扫到比pivot大的元素时，将其移动high指针指向的空位置，又轮到high指针向左扫描。直至两指针相遇
    static int partition(int[] A, int low, int high) {
        int pivot = A[low];//设置基准元素
        //初始low指向的视为空位置
        while(low < high) {
            while(low<high && A[high]>=pivot)
                --high;
            A[low]=A[high];//high指针向左扫描，扫描到比基准小的元素移到左端low指向的空位置，移动后high指向的视为空位置
            while(low<high && A[low]<=pivot)
                ++low;
            A[high]=A[low];//low指针向右扫描，扫描到比基准大的元素移到右端high指向的空位置，移动后low指向的视为空位置
        }
        A[low]=pivot;//无论是low遇到high 还是high遇到low，相遇位置一定是一个空位，即基准元素最终存放位置
        return low;//返回存放基准元素的位置
    }
}
/**
 * 简评：快排可以说是最常用的排序算法，代码简洁易实现，且其综合性能在内部排序算法中十分优异，
 * 与堆排序的跳跃式数组访问方式相比，快排的局部顺序访问显然对cpu缓存更加友好，另外堆排序在每次建堆的过程中会打乱数据原有的相对先后顺序，导致数据的有序度降低，
 * 比如对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。而快速排序数据交换的次数不会比逆序度多，因此快排相比堆排序交换数据的次数更少
 */